package 序列;

public class 最长回文子串 {
    public static void main(String[] args) {

    }

    public static String longestPalindrome(String s){
        if(s.length() < 2){
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        Boolean[][] dp = new Boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for (int L = 2; L <= s.length(); L++) {
            for (int i = 0; i < s.length(); i++) {
                int j = i + L - 1;
                if(s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    //这一步是边界条件，当L=1，2，3是，只要知道chart(i) == chart(i) 则ij必然是回文串。
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j] && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }

        return s.substring(begin, begin + maxLen);
    }
}
